In this lesson, we are going to study the Cycle Sort algorithm, which is one of the less commonly used sorting algorithms, but surprisingly useful in programming interviews.
The Theory
The cycle sort algorithm is an in-place sorting algorithm. This means that no external data structure (such as a list or heap) is required to perform the cycle sort operation.
The underlying assumption for the cycle sort algorithm is that an unsorted list is similar to a graph, where nodes are connected with edges. We can assume that a relationship between nodes A and B exists if-- in order to sort the array-- the element present at node A should be at the index of node B when rotated.
This is the big idea: Given an element a, we can find the index at which it will occur in the sorted list by simply counting the number of elements in the entire list that are smaller than a.
Of course, it's always hard to understand a new technique at first in abstract, so let's see cycle sort in action with the help of an example.
Suppose we have the following list or array of elements:
1[9, 4, 6, 8, 14, 3]